<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 5. Потоки.Advanced</h2>
<ol>
  <li>Алгоритм Диница</li>
  <ol>
    <li>Описание алгоритма, реализации</li>
    <li>Доказательство сложности O(V<sup>2</sup>E)</li>
    <li>Тест, на котором сложность достигается (а заодно тест против Эдмондса-Карпа)</li>
    <li>Спаривание с масштабированием: O(VElogC)</li>
  </ol></li>
  <li>Проталкивание предпотока</li>
  <ol>
    <li>Определение высотной функции, предпотока</li>
    <li>Наивный алгоритм (текущее ребро, ищем вершину с избытком, толкаем)</li>
    <li>Корректность (работает конечное время, в конце работы нет пути из истока в сток)</li>
    <li>Оценка времени работы: O(nm) + "количество холостых просмотров"</li>
    <li>Алгоритм за O(n<sup>3</sup>): пока где-то есть избыток перебираем вершины в произвольном порядке и толкаем.</li>
    <li>High-Level optimization</li>
    <li>Global-Relabeling optimization</li>
    <li>Простая для реализации версия алгоритма ~O(nm).</li>
  </ol></li>
  <li>MinCost поток</li>
  <ol>
    <li>За O(fnm) Форд-Беллманом.</li>
    <li>За O(fmlogn) Дейкстрой с потенциалами.</li>
    <li>Минимальная по весу циркуляция (mincost поток: |f| = 0)</li>
    <li>MinCost поток за полиномилальное время: цикл минимального среднего веса</li>
    <li>Цикл минимального среднего веса O(VElogM) (бинпоиск по ответу)</li>
    <li>Цикл минимального среднего веса O(VE)</li>
    <li>Задачи на MinCost: у нас есть k автоматов, выполнить задание i --- занять делом один из автоматов в моменты времени [L<sub>i</sub>..R<sub>i</sub>], у каждого задания есть стоимость. Выполнить задания максимальной суммарной стоимости.</li>
  </ol></li>
  <li>Тонкости работы с потокам и mincost потоками</li>
  <ol>
    <li>Ориентированный граф</li>
    <li>Неориентированный граф</li>
    <li>Задача поиска k путей</li>
  </ol></li>
  <li>[L,R] поток</li>
  <ol>
    <li>Избытки и недостатки: создали фиктивный сток и исток</li>
    <li>Поиск mincost потоком</li>
    <li>Поиск за O(flow)</li>
  </ol></li>
  <li>Задачи на разрезы</li>
  <ol>
    <li>Найти подграф с максимальной средней степенью вершины</li>
  </ol></li>
</ol>
